/************************************************************************************************
 * test examples of 100 interesting program in C
 * test 034.c
 * 1~20 the ring with prime couples
 ***********************************************************************************************/

#include <stdio.h>
#include <string.h>

/*
 * this solution don't clear all same rings, how to?
 */

#define MAX 20

int p[MAX][MAX];

int isPrime(int n)
{
	if (n < 2) return(0);
	else if (n == 2) return(1);
	else if (n%2 == 0) return(0);
	int i = 0;
	for (i = 3; i <= n/2; i += 2)
		if (n%i == 0) return(0);
	return(1);
}

int setPrimeArray()
{
	memset(p, 0, sizeof(int)*MAX*MAX);
	int i = 0, j = 0;
	for (i = 1; i <= MAX; i++)
	{
		int curr = 0;
		for (j = 1; j <= MAX; j++)
		{
			if (i == j) continue;
			if (isPrime(i+j))
				p[i-1][curr++] = j;
		}
	}
}

int printPrimeArray()
{
	int i = 0, j = 0;
	for (i = 1; i <= MAX; i++)
	{
		printf("%2d: ", i);
		for (j = 1; j <= MAX && p[i-1][j-1] != 0; j++)
			printf("%3d", p[i-1][j-1]);
		printf("\n");
	}
}

int ring[MAX];
int used[MAX];

// m is couple with n
int isCouple(int m, int n)
{
	int i = 0;
	for (i = 0; p[n-1][i] != 0; i++)
		if (p[n-1][i] == m) return(1);
	return(0);
}

int printRing()
{
	int i = 0;
	for (i = 0; i < MAX; i++)
		printf("%3d", ring[i]);
	printf(";\n");
}

int fillRing(int n, int pos)
{
	// do
	ring[pos-1] = n;
	used[n-1] = 1;
	
	int flag = 0;

	if (pos == MAX)
	{
		if (isCouple(n, ring[0]))
		{
			//printRing();
			flag = 1;
		}
		else
			flag = 0;
	}
	else
	{
		// Prunning:
		// to check whether there is still number left can be filled as the last element
		// which means this number is a couple with ring[0]
		// but this pruning is not useful, only slow down the program
		// if (!isTailCut())	
		{
			int i = 0;
			for (i = 0; p[n-1][i] != 0; i++)
			{
				if (used[p[n-1][i]-1] == 0)
				{
					flag += fillRing(p[n-1][i], pos+1);
				}
			}
		}
	}

	// undo, don't forget undo before any "return"
	used[n-1] = 0;
	ring[pos-1] = 0;

	return(flag);
}
int main()
{
	setPrimeArray();
	printPrimeArray();

	memset(ring, 0, sizeof(int)*MAX);
	memset(used, 0, sizeof(int)*MAX);

	int count = 0;
	count = fillRing(1, 1);
	printf("Total %d rings with prime couples\n", count);
}
